package demo7;

import java.util.PriorityQueue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Solution {
    //1.层数最深叶子节点的和(BFS)
    public int deepestLeavesSum(TreeNode root) {
        if(root == null) {
            return 0;
        }
        //BFS层序遍历
        Queue<TreeNode> queue = new LinkedList<>();
        int ret = 0;
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            int sum = 0;
            while(size > 0) {
                TreeNode node = queue.poll();
                if(node.left != null) {
                    queue.offer(node.left);
                }
                if(node.right != null) {
                    queue.offer(node.right);
                }
                size--;
                sum += node.val;
            }
            ret = sum;
        }
        return ret;
    }
    //3.二叉树的坡度(dfs)
    private int sum;
    public int findTilt(TreeNode root) {
        if(root == null) {
            return 0;
        }
        //看左右子树的坡度
        int left = tilt(root.left);
        int right = tilt(root.right);
        sum += Math.abs(left - right);
        //再递归的去看左右子树各自坡度
        findTilt(root.left);
        findTilt(root.right);
        return sum;
    }
    private int tilt(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return tilt(root.left) + tilt(root.right) + root.val;
    }
    //3. 二叉树的坡度(dfs优化)
    private int sum;
    public int findTilt(TreeNode root) {
        tilt(root);
        return sum;
    }
    private int tilt(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int left = tilt(root.left);
        int right = tilt(root.right);
        sum += Math.abs(left - right);
        return left + right + root.val;
    }
    //8.最长同值路径(dfs)
    private int ret;
    public int longestUnivaluePath(TreeNode root) {
        dfs(root);
        return ret;
    }
    private int dfs(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int l = dfs(root.left);
        int r = dfs(root.right);
        int left = 0;
        int right = 0;
        if(root.left != null && root.left.val == root.val) {
            left = l + 1;
        }
        if(root.right != null && root.right.val == root.val) {
            right = r + 1;
        }
        ret = Math.max(ret, left + right);
        return Math.max(left, right);
    }
    //9.在二叉树中增加一行(BFS层序遍历)
    public TreeNode addOneRow(TreeNode root, int val, int depth) {
        if(depth == 1) {
            TreeNode tree = new TreeNode(val);
            tree.left = root;
            return tree;
        }
        //BFS层序遍历
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        for(int i = 1; i < depth - 1; i++) {
            int size = queue.size();
            while(size > 0) {
                TreeNode tree = queue.poll();
                if(tree.left != null) {
                    queue.offer(tree.left);
                }
                if(tree.right != null) {
                    queue.offer(tree.right);
                }
                size--;
            }
        }
        //queue拿到了depth - 1层
        while(!queue.isEmpty()) {
            TreeNode tree = queue.poll();
            TreeNode node1 = new TreeNode(val);//新结点1
            TreeNode node2 = new TreeNode(val);//新结点2
            node1.left = tree.left;
            node2.right = tree.right;
            tree.left = node1;
            tree.right = node2;
        }
        return root;
    }
    //10.从根到叶的二进制数之和(dfs)
    public int sumRootToLeaf(TreeNode root) {
        return dfs(root, 0);
    }
    private int dfs(TreeNode root, int sum) {
        if(root == null) {
            return 0;
        }
        sum = (sum << 1) | root.val;
        if(root.left == null && root.right == null) {
            return sum;
        }
        return dfs(root.left, sum) + dfs(root.right, sum);
    }
}
//2.数据流中的第 K 大元素(top-k)
class KthLargest {
    private PriorityQueue<Integer> queue;
    private int k;
    public KthLargest(int k, int[] nums) {
        //求第K个最大的，就维护一个小堆
        this.k = k;
        this.queue = new PriorityQueue<>();
        for(int i = 0; i < nums.length; i++) {
            if (i < k) {
                queue.offer(nums[i]);
            } else if (queue.peek() < nums[i]) {
                queue.poll();
                queue.offer(nums[i]);
            }
        }
    public int add(int val) {
        if(queue.isEmpty() || queue.size() < k) {
            queue.offer(val);
        }
        else if(queue.peek() < val) {
            queue.poll();
            queue.offer(val);
        }
        return queue.peek();
    }
    //4.面试题 04.03. 特定深度节点链表(BFS)
    public ListNode[] listOfDepth(TreeNode tree) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<ListNode> list = new LinkedList<>();
        queue.offer(tree);
        while(!queue.isEmpty()) {
            int size = queue.size();
            ListNode head = new ListNode(-1);//虚拟结点
            ListNode cur = head;
            while(size > 0) {
                TreeNode root = queue.poll();
                ListNode curNext = new ListNode(root.val);
                cur.next = curNext;
                cur = curNext;
                if(root.left != null) {
                    queue.offer(root.left);
                }
                if(root.right != null) {
                    queue.offer(root.right);
                }
                size--;
            }
            list.add(head.next);
        }
        int len = list.size();
        ListNode[] ret = new ListNode[len];
        for(int i = 0; i < len; i++) {
            ret[i] = list.get(i);
        }
        return ret;
    }
    //5.两棵二叉搜索树中的所有元素(暴力)
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> ret = new LinkedList<>();
        List<Integer> list1 = new LinkedList<>();
        List<Integer> list2 = new LinkedList<>();
        dfs(root1, list1);
        dfs(root2, list2);
        //合并
        int l1 = 0;
        int l2 = 0;
        int len1 = list1.size();
        int len2 = list2.size();
        while(l1 < len1 && l2 < len2) {
            if(list1.get(l1) < list2.get(l2)) {
                ret.add(list1.get(l1));
                l1++;
            }else {
                ret.add(list2.get(l2));
                l2++;
            }
        }
        while(l1 < len1) {
            ret.add(list1.get(l1));
            l1++;
        }
        while(l2 < len2) {
            ret.add(list2.get(l2));
            l2++;
        }
        return ret;
    }
    private void dfs(TreeNode root, List<Integer> list) {
        if(root == null) {
            return;
        }
        dfs(root.left, list);
        list.add(root.val);
        dfs(root.right, list);
    }
    //5.两棵二叉搜索树中的所有元素(换成ArrayList速度从5%变到100%)
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> ret = new ArrayList<>();
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        dfs(root1, list1);
        dfs(root2, list2);
        //合并
        int l1 = 0;
        int l2 = 0;
        int len1 = list1.size();
        int len2 = list2.size();
        while(l1 < len1 && l2 < len2) {
            if(list1.get(l1) < list2.get(l2)) {
                ret.add(list1.get(l1));
                l1++;
            }else {
                ret.add(list2.get(l2));
                l2++;
            }
        }
        while(l1 < len1) {
            ret.add(list1.get(l1));
            l1++;
        }
        while(l2 < len2) {
            ret.add(list2.get(l2));
            l2++;
        }
        return ret;
    }
    private void dfs(TreeNode root, List<Integer> list) {
        if(root == null) {
            return;
        }
        dfs(root.left, list);
        list.add(root.val);
        dfs(root.right, list);
    }

    //6.面试题 04.06. 后继者(不够优化)
    private boolean flag = false;//false表示还未找到p结点
    private TreeNode target;
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        dfs(root, p);
        return target;
    }
    private void dfs(TreeNode root, TreeNode p) {
        if(root == null) {
            return;
        }
        dfs(root.left, p);
        if(flag) {
            target = root;
            flag = false;
            return;
        }
        if(root == p) {
            flag = true;
        }
        dfs(root.right, p);
    }
    //7.面试题 04.06. 后继者(利用二叉搜索树特性优化)
        public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
            if(root == null) {
                return null;
            }
            //若当前结点的值小于等于p，那么必然在右子树
            if(root.val <= p.val) {
                return inorderSuccessor(root.right, p);
            }
            //root.val > p.val有两种可能
            //一是左树可能还有更小但是满足的
            //二是左树为空，所以当前结点即为所求
            TreeNode ans = inorderSuccessor(root.left, p);
            return ans == null ? root : ans;
        }

}